1. Field of the Invention
This invention relates to sharing of resources and more particularly to more efficient allocation of resources.
2. Description of the Related Art
Arbitration is needed if a shared resource is simultaneously requested by several users of that resource and access to the resource can only be granted to one user at a time. FIG. 1 shows a 2×2 crossbar switch coupling two input ports IP1 and IP2 with two output ports OP1 and OP2. In the example of FIG. 1, arbitration is required to allocate the output ports OP1 and OP2 to the input ports IP1 and IP2 since the input ports can simultaneously request the same output port and an output port can be utilized for a data transfer only by one input port at a time.
FIG. 2 shows exemplary timing of an arbitrated access to a shared resource such as may occur when IP1 and IP2 both request use of the same output port for the same time period. As is typical in arbitrated system, access to the resource is granted in fixed discrete time intervals 201 and 203. Arbitration (ARB1 and ARB2) typically also occurs in fixed discrete intervals 205 and 207. Fixed discrete intervals are typically used for arbitration and access intervals to make coordination with other system resources simpler. Note that arbitration overlaps access in the example shown in FIG. 2. For example, arbitration period 207 (ARB2) for access interval 203 (ACC2) overlaps access period 201 (ACC1). In the simple example of FIG. 2, there are two users issuing requests REQA and REQB for one shared resource. Requests REQA and REQB are considered during arbitration period ARB1 and request REQA is granted use of the shared resource during access period ACC1. REQB is again considered during arbitration period ARB2 and REQB is granted access to the shared resource during access period ACC2.
Unfortunately, there is unwanted delay between the time a request is generated (e.g. at 209) and the time the actual access begins. Assuming requests are generated at arbitrary times during an access interval and further assuming that there are no conflicts for the requested resource, the average delay is half the access interval plus the arbitration time. In the worst case, the delay can be the full interval plus the arbitration time.
Referring to FIG. 3, the worst case delay, given the assumptions above, is shown for request REQB, which misses arbitration cycle ARB2 and as a result has to wait to be considered in arbitration cycle ARB3. Note also that as a result, access interval ACC2 is not granted to anyone and therefore the resource goes unutilized during that access interval. Request REQB is subsequently granted the resource for use during access interval ACC3. The delay encountered by request REQB is unwanted since the delay increases the latency of the data, causes underutilization of the resource and can reduce throughput.
It would be desirable to provide an arbiter that more efficiently shares the available resources among the various users that request their use.